Data processing is now used in every field in society. Processing by computers and other processing equipment computes and manipulates all kinds of data to produce meaningful results used to make predictions, take decisions, and control systems. One important field of data processing is optimization. When certain processing is to be performed, it is imperative to minimize the resources and cost, and to find a solution that optimizes the result of the processing. This issue is of clear importance.
Linear programming is a representative example of an optimization problem. Linear programming finds the values of variables that maximize or minimize an evaluation function represented by a linear sum of a plurality of continuous variables under constraints also represented by linear sums, and is used in a variety of fields, such as production scheduling of products. Superior algorithms, such as the simplex method and interior point method, are known for linear programming and make it possible to efficiently solve problems, even those with hundreds of thousands of variables.
However, many known optimization problems have variables that are not continuous values and instead take discrete values. Representative examples include the traveling salesman problem of finding the shortest route that passes a plurality of cities in turn and returns to the start, and the knapsack problem of finding a combination that maximizes a sum of values when packing different items into a knapsack. These problems are referred to as “discrete optimization problems” or “combination optimization problems”, and are known to present great difficulty when finding an optimal solution.
The principal reason why it is difficult to solve a discrete optimization problem is that due to the respective variables taking only discrete values, it is not possible to use methods that reach the optimal solution by continuously changing variables in a direction in which an evaluation function improves. In addition to the combination of values of variables that produces an optimal value (this combination is referred to as an “optimal solution”, a “global solution”, or a “global minimum”), there are a large number of combinations that provide a local extreme value for an evaluation function (these combinations are referred to as a “minimal” (or “maximal”), a “local solution”, or a “local minimum”). This means that in order to reliably obtain an optimal solution, the use of brute-force type methods is unavoidable, which results in the calculation time becoming very long. Among discrete optimization problems, there are many problems where the calculation time taken to obtain the optimal solution is expected to increase exponentially with respect to the size of the problem (that is, the number of variables in the problem). These problems are referred to as “NP (Non-deterministic Polynomial)-hard” problems in computational complexity theory. The traveling salesman problem and the knapsack problem mentioned above are both examples of NP-hard problems.
As described above, it is very difficult to reliably obtain an optimal solution to a discrete optimization problem. For this reason, algorithms that make use of properties that are peculiar to individual problems have been proposed for solving discrete optimization problems that are of practical importance. As described above, since the calculation time taken to obtain a precise solution is expected to increase exponentially for many discrete optimization problems, many practical approaches are approximation algorithms, and although an optimal solution is not achieved, it is still possible to obtain a solution where the value of the evaluation function is close to the optimal value.
In contrast to approximation algorithms that are specific to certain problems, there are also approximation algorithms that do not use specific properties of problems and are instead compatible with a wide range of problems. These algorithms are referred to as “metaheuristics”, with simulated annealing (or “SA”), genetic algorithms, and neural networks as representative examples. Although these metaheuristics potentially have lower efficiency than solutions that make effective use of the properties of a problem, they are expected to find a solution faster than algorithms that obtain a precise solution.
Out of these methods, the present embodiments relate to simulated annealing.
Simulated annealing is one type of Monte Carlo method and uses random numbers to stochastically find a solution. As one example, the following describes a problem where the value, here referred to as “energy”, of an evaluation function to be optimized is to be minimized. As an alternative, the value is maximized by changing the signs used in the evaluation function.
Starting from an initial state where a discrete value is assigned to each variable, a state that is close to the present state (here meaning a combination of values of variables) is selected from the present state. As one example, a state where only one of the variables has changed is selected, and this state transition is considered. The change in energy for this state transition is calculated, and depending on the calculated value, it is stochastically decided whether to adopt the state transition and change states or whether to not adopt the transition and keep the original state. If the probability of adoption is set larger for cases where the energy falls than for cases where the energy rises, on average the state will change in a direction in which the energy falls, so that state transitions to a more appropriate state are expected to occur as time passes. There is also the possibility of ultimately obtaining the optimal solution or an approximate solution that provides an energy that is close to the optimal value. By comparison, with a deterministic configuration where transitions are adopted when energy falls and are not adopted when the energy rises, although the energy will change so as to monotonously decrease over time in the broadest sense, such changes will stop occurring when a local minimum is reached. Since discrete optimization problems have a very large number of local minimums as described above, the state will almost certainly get caught at a local minimum which is not very close to the optimal value. For this reason, it is important to stochastically decide whether transitions are adopted.
For the simulated annealing method, it has been established that when the adoption (permission) probability of a state transition is decided as indicated below, the state will reach the optimal solution when the limit on time (i.e., the number of iterations) is set at infinity.
(1) The permission probability p of a state transition is determined relative to the change in energy (or “energy decrease”) (−ΔE) caused by the state transition according to either of the functions f( ) below.
                              p          ⁡                      (                                          Δ                ⁢                                                                  ⁢                E                            ,              T                        )                          =                  f          ⁡                      (                                          -                Δ                            ⁢                                                          ⁢                              E                /                T                                      )                                              (                  1          ⁢                      -                    ⁢          1                )                                                      f            metro                    ⁡                      (            x            )                          =                              min            ⁡                          (                              1                ,                                  e                  x                                            )                                ⁢                                          ⁢                      (                          Metropolis              ⁢                                                          ⁢              Method                        )                                              (                  1          ⁢                      -                    ⁢          2                )                                                      f            Gibbs                    ⁡                      (            x            )                          =                              1                          1              +                              e                                  -                  x                                                              ⁢                                          ⁢                      (                          Gibbs              ⁢                                                          ⁢              Method                        )                                              (                  1          ⁢                      -                    ⁢          3                )            
Here, T is a parameter called a “temperature” that changes as indicated below.
(2) The temperature T logarithmically decreases with respect to the number of iterations t as expressed by the following equation.
                    T        =                                            T              0                        ⁢                          log              ⁡                              (                c                )                                                          log            ⁡                          (                              t                +                c                            )                                                          (        2        )            
Here, T0 is the initial temperature and is preferably set at a sufficiently large value for the problem to be solved.
When the permission probability expressed by expressions in the above (1) is used, once a sufficient number of iterations have been performed and a steady state is reached, the occupation probability of each state will follow a Boltzmann distribution for a thermal equilibrium in thermodynamics. Since the occupation probability of a low energy state will increase as the temperature gradually decreases from the initial high temperature, a low energy state is usually obtained when the temperature has fallen sufficiently. Since this is similar to the changes in state that occur when a material is annealed, this method is called “simulated annealing”. At this time, state transitions where the energy increases occur stochastically, which corresponds to the phenomenon of thermal excitation in physics.
As described above, although simulated annealing obtains an optimal solution when the number of iterations is infinite, in reality a finite number of iterations are used to obtain a solution, which means that there is no guarantee that the optimal solution will be found. Also, since the fall in temperature in the expression given above is very slow, the temperature will not fall sufficiently in a finite time. Accordingly, during actual simulated annealing, it is common for the temperature to not change logarithmically and instead be decreased rapidly.
FIG. 14 depicts the conceptual configuration of an optimization apparatus that uses simulated annealing. Although a case where a plurality of state transition candidates are generated is described later, the following description focuses on a basic form of simulated annealing where transition candidates are generated one at a time.
The optimization apparatus 10 has a state holding unit 11 that first holds a current state S (i.e., the values of a plurality of state variables). The optimization apparatus 10 also includes an energy calculating unit 12 that calculates a change in energy {−ΔEi} of each state transition when a state transition from the present state S has occurred due to a change in any of a plurality of state variables. The optimization apparatus 10 also includes a temperature control unit 13 that controls the temperature T and a transition control unit 14 for controlling changes in state.
Based on the temperature T, the change in energy {−ΔEi}, and a random number, the transition control unit 14 stochastically decides whether to accept any of a plurality of state transitions according to a relative relationship between the change in energy {−ΔEi} and the thermal excitation energy.
When subdivided, the transition control unit 14 includes a candidate generating unit 14a that generates a state transition candidate and a transition assessor 14b that stochastically judges whether to permit each state transition candidate based on the change in energy {−ΔEi} and the temperature T. In addition, the transition control unit 14 includes a transition deciding unit 14c that decides a candidate to be adopted out of the permitted candidates and a random number generating unit 14d that generates a stochastic variable.
The operation in one iteration is as follows. First, the candidate generating unit 14a generates one or a plurality of candidates (with the candidate numbers {Ni}) for state transitions from the present state S held in the state holding unit 11 to a next state. The energy calculating unit 12 calculates the change in energy {−ΔEi} for each state transition given as a candidate using the present state S and the state transition candidate. The transition assessor 14b uses the temperature T generated by the temperature control unit 13 and the stochastic variable (random number) generated by the random number generating unit 14d to permit state transitions with the permission probability in expressions described in the above (1) in accordance with the change in energy {−ΔEi} of each state transition. The transition assessor 14b outputs a transition permission value {fi} indicating whether each state transition is to be accepted (this is referred to in the following description as “permission” of a state transition). When a plurality of state transitions are permitted, the transition deciding unit 14c randomly selects one of the state transitions using a random number. The transition deciding unit 14c then outputs the transition number N of the selected state transition and the transition permission value f. When there is a permitted state transition, the values of the state variables stored in the state holding unit 11 are updated in accordance with the adopted state transition.
Starting from an initial state, the iteration described above is repeated while lowering the temperature at the temperature control unit 13 until an end judgment condition is satisfied, such as reaching a certain number of iterations or the energy falling below a certain value, at which point the operation ends. The solution outputted from the optimization apparatus 10 is the state when the operation ends. In practice, however, the temperature will not reach zero in a finite number of iterations, so that the occupation probabilities of states at the end will have a distribution represented by a Boltzmann distribution or the like and will not necessarily be the optimal value or a good solution. Accordingly, a practical method of holding a state with the lowest energy obtained during the iterations and ultimately outputting this state as the solution is used.
FIG. 15 is a circuit-level block diagram of an example configuration of a computing portion used for a transition control unit, and in particular a transition assessor, in regular simulated annealing where candidates are generated one at a time.
The transition control unit 14 includes a random number generating circuit 14b1, a selector 14b2, a noise table 14b3, a multiplier 14b4, and a comparator 14b5.
The selector 14b2 selects and outputs a change in energy, out of the change in energy {−ΔEi} calculated for every state transition candidate, which corresponds to the transition number N that is a random number generated by the random number generating circuit 14b1.
The functions of the noise table 14b3 are described later. As examples of the noise table 14b3, it is possible to use a memory such as RAM (Random Access Memory) and flash memory.
The multiplier 14b4 outputs a product (corresponding to the thermal excitation energy described earlier) produced by multiplying the value outputted by the noise table 14b3 and the temperature T.
The comparator 14b5 outputs, as a transition permission value f, a comparison result produced by comparing the multiplication result outputted by the multiplier 14b4 and −ΔE that is the change in energy selected by the selector 14b2.
Although the transition control unit 14 depicted in FIG. 15 is basically a direct implementation of the functions described earlier, the mechanism for permitting a state transition according to a permission probability expressed by expressions in the above (1) has not been touched upon and so will be described here.
A circuit that outputs one with a permission probability p and outputs zero with a probability of (1-p) may be realized by inputting the permission probability p into an input A of a comparator that has two inputs A and B and is configured to output one when A>B and output zero when A<B, and inputting a uniform random number that takes a value in the interval [0,1) into the input B. Accordingly, by inputting a value of permission probability p calculated from the change in energy and the temperature T using expressions in the above (1) into the input A of this comparator, the function described above is realized.
In other words, when f is a function used in expressions in the above (1) and u is a uniform random number that takes a value in the interval [0,1), a circuit that outputs one when f(−ΔE/T) is larger than u realizes the function described above.
While the above configuration will work, it is also possible to realize the same function via the following modification. When two numbers are operated using the same monotonically increasing function, the relative magnitudes of the two values will not change. Accordingly, the output of a comparator will not change when the two inputs are operated using the same monotonically increasing function. When an inverse function f−1 of a function f is used as the monotonically increasing function, a circuit that outputs one when −ΔE/T is larger than f−1(u) may be used. Also, since the temperature T is positive, a circuit that outputs one when −ΔE is larger than Tf−1(u) may be used. The noise table 14b3 in FIG. 15 is a conversion table for realizing the inverse function f−1(u) and is a table that outputs values of the following function for an input of discrete values in the interval [0, 1).
                                          f            metro                          -              1                                ⁡                      (            u            )                          =                  log          ⁡                      (            u            )                                              (                  3          ⁢                      -                    ⁢          1                )                                                      f            Gibbs                          -              1                                ⁡                      (            u            )                          =                  log          ⁡                      (                          u                              1                -                u                                      )                                              (                  3          ⁢                      -                    ⁢          2                )            
Although a latch that holds a judgment result, a state machine that generates timing for the latch, and the like are also present in the transition control unit 14, such elements have been omitted from FIG. 15 to simplify the drawing.
FIG. 16 depicts an operation flow of a transition control unit according to a conventional example. The operation flow includes a step that selects one state transition as a candidate (S1), a step that decides whether the state transition is permitted according to a comparison between the change in energy for the state transition and a product of a temperature and a random number (S2), and a step that adopts the state transition when the state transition is permitted and does not adopt the state transition when the state transition is not permitted (S3).
As is clear from the above description, simulated annealing has wide applicability and is a very advantageous method. However, since the temperature is slowly lowered, there is the problem that the calculation time is comparatively long. In addition to this problem regarding the lowering of temperature, there is the problem that it is difficult to make appropriate adjustments. This will now be described with reference to FIG. 17.
On a path from the initial state to an optimal solution or an approximate solution, there will be many local minimums that are poor approximations. To escape from these local minimums sufficiently quickly, the temperature needs to be high enough for sufficient thermal excitation. At high temperatures however, the energy spread in a Boltzmann distribution is large, so that the difference in occupation probability between an optimal solution or a good approximate solution with a low energy (hereinafter simply referred to as a “good solution”) and the local minimum that is a poor approximation with a relatively high energy (hereinafter simply referred to as a “poor solution”) is small. For this reason, even when it is possible to escape from a local minimum, the escaped-to destination will be distributed among the many other poor solutions, so that the probability of reaching a good solution is very low. To increase the occupation probabilities of good solutions, a low temperature where the thermal excitation energy becomes sufficiently low compared to the difference in energy from a poor solution is preferable. However, since the thermal excitation energy is low, the probability of overcoming energy peaks on the route is very low, resulting in state transitions hardly occurring. Accordingly, the occupation probabilities of good solutions are gradually increased by providing some ability to overcome peaks and slowly passing through intermediate temperatures where some difference in occupation probability is produced. When the temperature is lowered too slowly, there will be little reduction in temperature in a given period, so that the occupation probabilities of good solutions will ultimately not improve. Conversely, when the temperature is lowered too rapidly, the temperature will fall before an escape is made from the local minimum and the system will be trapped at a poor solution. Accordingly, the further the temperature has fallen, the smaller the changes to be made in temperature to provide sufficient time to reach a Boltzmann distribution for that temperature.
With conventional simulated annealing, to escape from a local minimum using only thermal excitation due to temperature, it is desirable to slowly lower the temperature and to make appropriate adjustments to how the temperature is lowered in keeping with the problem to be optimized.
Note that when searching for a procedure by repeatedly generating and evaluating image processing procedures that input original images and sample images to be recognized and perform recognition, there is a technique that uses simulated annealing with a taboo list for preventing solutions that have been searched from being re-evaluated.
There is also a technique that implements a Boltzmann machine with a function that performs temperature control and calculates changes in energy. See, for example, the following documents.
Japanese Laid-open Patent Publication No. 2005-258609
Japanese Laid-open Patent Publication No. 2001-250102
Christian R. Schneider et al., “Analog CMOS Deterministic Boltzmann Circuits” JSSC, VOL. 28, No. 8, pp. 907-914, August 1993
As described above, the long time taken to escape from local minimums is a major cause of prolonging of the calculation time of simulated annealing. Also, even when a state transition is performed to escape from a local minimum, it is not possible to fully escape from the local minimum with one state transition and the risk of a return to the prior state remains, which is also a factor in the long time taken to escape from local minimums.